//===- Phase1.cpp - Phase 1 of CS6241 ------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file is the source code of project phase 1 of CS6241
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "phase1"
#include "llvm/Pass.h"
#include "llvm/Module.h"
#include "llvm/Instructions.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Type.h"
#include "llvm/Use.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Operator.h"
#include "llvm/Support/CFG.h"
#include "llvm/Analysis/Dominators.h"
#include <list>
#include <map>
#include <set>
#include <vector>
#include <limits>

#define PART_II  1 
#define PART_III 1 

using namespace llvm; 
using namespace std;

typedef struct CheckVal {
  Value* index;
  int32_t bound;
  bool isUpper;
} CheckValTy;

typedef pair<Instruction*, CheckValTy> CheckPairTy;

namespace {
  struct classcomp1 {
    bool operator() (const CheckValTy& lhs, const CheckValTy& rhs) const {
      if (lhs.index < rhs.index) return true;
      else if (lhs.index == rhs.index) {
        if (lhs.bound < rhs.bound) return true;
	else if (lhs.bound == rhs.bound) {
	  if (lhs.isUpper < rhs.isUpper) return true;
	}
      }

      return false;
    }
  };

  struct classcomp2 {
    bool operator() (const CheckPairTy& lhs, const CheckPairTy& rhs) const {
      return lhs.first < rhs.first;
    }
  };

}

typedef set<BasicBlock*> NDTy;
typedef list<CheckPairTy >CheckTy;
typedef map<BasicBlock*, CheckTy*> BblCheckMapTy;
typedef set<CheckValTy, classcomp1>CheckSetTy;
typedef map<BasicBlock*, CheckSetTy*>BblCheckSetMapTy;
typedef list<Loop *>LoopQueueTy;
typedef pair<int32_t, int32_t> RangeTy;
typedef map <Value*, RangeTy*> ValRangeTy;
typedef map<BasicBlock*, ValRangeTy*> BblRangeMapTy;

namespace {
  void dumpSet (CheckSetTy *checkSet) {
    for (CheckSetTy::iterator I = checkSet->begin(), E = checkSet->end(); I != E; ++I) {
      Value *index = I->index;
      int32_t bound = I->bound;
      bool isUpper = I->isUpper;

      index->dump();
      cout << bound << endl;

      if (isUpper) cout << "Upper" << endl;
      else cout << "Lower" << endl;
    }

    cout << endl;
  }

  void unionIntoSet (CheckSetTy *checkSet, const CheckValTy *check) {
    Value* index = check->index;
    int32_t bound = check->bound;
    bool isUpper = check->isUpper;

    for (CheckSetTy::iterator I = checkSet->begin(), E = checkSet->end(); I != E; ++I) {
      Value *index2 = I->index;
      int32_t bound2 = I->bound;
      bool isUpper2 = I->isUpper;

      if (isUpper && isUpper2) { 
        if (index == index2) {
          if (bound < bound2) {
	    CheckValTy tmp;
	    tmp.index = index;
	    tmp.bound = bound;
	    tmp.isUpper = true;
            checkSet->erase(I);
            checkSet->insert(tmp);
          }
      
          return;
        }
      }
      else if (!isUpper && !isUpper2) { 
        if (index == index2) {
          if (bound > bound2) {
	    CheckValTy tmp;
	    tmp.index = index;
	    tmp.bound = bound;
	    tmp.isUpper = false;
            checkSet->erase(I);
            checkSet->insert(tmp);
          }
      
          return;
        }
      }	
    }

    checkSet->insert(*check);
  }

  void unionSet (CheckSetTy *checkSet1, CheckSetTy *checkSet2) {
    for (CheckSetTy::iterator I = checkSet2->begin(), E = checkSet2->end(); I != E; ++I) {
      unionIntoSet(checkSet1, &*I);
    }
  }

  void intersectSet (CheckSetTy *checkSet1, CheckSetTy *checkSet2) {
STEP1:
    for (CheckSetTy::iterator I1 = checkSet1->begin(), E1 = checkSet1->end(); I1 != E1; ++I1) {
      Value* index1 = I1->index;
      bool isUpper1 = I1->isUpper;
      bool found = false;

      for (CheckSetTy::iterator I2 = checkSet2->begin(), E2 = checkSet2->end(); I2 != E2; ++I2) {
        Value* index2 = I2->index;
        bool isUpper2 = I2->isUpper;

        if (index1 == index2  && isUpper1 == isUpper2) {
          found = true;

	  break;
        }
      }

      if (!found) {
        checkSet1->erase(I1);
	goto STEP1;
      }
    }

    for (CheckSetTy::iterator I2 = checkSet2->begin(), E2 = checkSet2->end(); I2 != E2; ++I2) {
      Value* index2 = I2->index;
      int32_t bound2 = I2->bound;
      bool isUpper2 = I2->isUpper;

      for (CheckSetTy::iterator I1 = checkSet1->begin(), E1 = checkSet1->end(); I1 != E1; ++I1) {
        Value* index1 = I1->index;
        int32_t bound1 = I1->bound;
	bool isUpper1 = I1->isUpper;
     
        if (isUpper1 && isUpper2) {	
          if ( index1 == index2 ) {
	    if (bound1 < bound2) {
	      CheckValTy tmp;
	      tmp.index = index1;
	      tmp.bound = bound2;
	      tmp.isUpper = true;
              checkSet1->erase(I1);
	      checkSet1->insert(tmp);
	    }

	    break;
          }
	}
	else if (!isUpper1 && !isUpper2) {	
          if ( index1 == index2 ) {
	    if (bound1 > bound2) {
	      CheckValTy tmp;
	      tmp.index = index1;
	      tmp.bound = bound2;
	      tmp.isUpper = false;
              checkSet1->erase(I1);
	      checkSet1->insert(tmp);
	    }

	    break;
          }
	}
      }
    }
  }

  bool compareSet (CheckSetTy *checkSet1, CheckSetTy *checkSet2) {
    if (checkSet1->size() != checkSet2->size()) return true;

    for (CheckSetTy::iterator I1 = checkSet1->begin(), E1 = checkSet1->end(); I1 != E1; ++I1) 
      if (checkSet2->find(*I1) == checkSet2->end()) return true;
      
    return false;
  }

  Value* InsertCheckCall(vector<Value*> &Args, Instruction *InsertPos, bool isUpper) {
    Module *M = InsertPos->getParent()->getParent()->getParent();
    Function *CallFn;
    Value *RetVal;

    if (isUpper) CallFn = M->getFunction("checkUB"); else CallFn = M->getFunction("checkLB");

    RetVal = CallInst::Create(CallFn, Args.begin(), Args.end(), "", InsertPos);
   
    return RetVal;
  }

  void TransformMainFunction(Function *MainFn) {
    Module *M = MainFn->getParent();

    vector <const Type*> ParamTypes(2);
    ParamTypes[0] = Type::getInt32Ty(getGlobalContext());
    ParamTypes[1] = Type::getInt32Ty(getGlobalContext());

    const Type * ReturnTy = Type::getVoidTy(getGlobalContext());

    FunctionType *FTy = FunctionType::get(ReturnTy, ParamTypes, false);

    M->getOrInsertFunction("checkUB", FTy);
    M->getOrInsertFunction("checkLB", FTy);
  }

  bool isSubsumedBound(CheckValTy check1, CheckValTy check2) {
    Value *index1 = check1.index;
    Value *index2 = check2.index;
    int32_t bound1 = check1.bound;
    int32_t bound2 = check2.bound;
    bool isUpper1 = check1.isUpper;
    bool isUpper2 = check2.isUpper;

    if (isUpper1 && isUpper2) {
      if (bound1 >= bound2) {
        if (ConstantInt *CI1 = dyn_cast<ConstantInt>(index1)) {
          if (ConstantInt *CI2 = dyn_cast<ConstantInt>(index2)) 
            if (CI1->getSExtValue() == CI2->getSExtValue()) return true;
        }
        else if (!isa<ConstantInt>(index2)) {
          if (index1 == index2) return true;
        }
      }
    }
    else if (!isUpper1 && !isUpper2) {
      if (bound1 <= bound2) {
        if (ConstantInt *CI1 = dyn_cast<ConstantInt>(index1)) {
          if (ConstantInt *CI2 = dyn_cast<ConstantInt>(index2)) 
            if (CI1->getSExtValue() == CI2->getSExtValue()) return true;
        }
        else if (!isa<ConstantInt>(index2)) {
          if (index1 == index2) return true;
        }
      }
    }

    return false;
  }
}

namespace {
  struct InsertBoundChk : public FunctionPass {
  private:
    LoopInfo *LI;
    DominatorTree *DT;
    LoopQueueTy LoopQueue;
    bool isLoaded;

  public:
    static char ID; // Pass identification, replacement for typeid
    InsertBoundChk() : FunctionPass(&ID) {isLoaded = false;}
   
    void addLoopIntoQueue(Loop *L) {
      LoopQueue.push_front(L);

      const vector<Loop *> &subLoop = L->getSubLoops();

      for (size_t I = 0; I < subLoop.size(); ++I) {
        addLoopIntoQueue(subLoop[I]);
      }
    }

    virtual bool runOnFunction(Function &F) { 
      bool Change = false;

      if(!isLoaded) {
        TransformMainFunction(&F);
	isLoaded = true;
      }

      BblCheckMapTy BblCheckMap;
      BblCheckSetMapTy BusyGen, BusyIn, BusyOut;
      BblCheckSetMapTy AvailGen, AvailIn, AvailOut;
//      set<Value *> IndVars;
      CheckSetTy CheckDomain;

      /* Generate all Boundary Checks */
      for (Function::iterator blk = F.begin(), blke = F.end(); blk != blke; ++blk) {
        CheckTy *checkInBbl = new CheckTy; 
        BblCheckMap[blk] = checkInBbl;

        for (BasicBlock::iterator I = blk->begin(), E = blk->end(); I != E; ++I) {
  
          if (GetElementPtrInst *GI = dyn_cast<GetElementPtrInst>(&*I)) {
    	    User::op_iterator IDX = GI->idx_begin();
    	    User::op_iterator IDXE = GI->idx_end();
    
    	    if (IDX != IDXE) ++IDX;
    
    	    const Type * type = GI->getPointerOperandType()->getContainedType(0);
    
            for (; IDX != IDXE; ++IDX) {
              if (const ArrayType *AT = dyn_cast<ArrayType>(type)) {
                int32_t bound = AT->getNumElements();
             
	     	CheckValTy checkUB, checkLB;

		checkUB.index = IDX->get();
	        checkUB.bound = bound;
	        checkUB.isUpper = true;	

		checkLB = checkUB;
                checkLB.bound = 0;
		checkLB.isUpper = false;

		checkInBbl->push_back(make_pair(&*I, checkUB));
		checkInBbl->push_back(make_pair(&*I, checkLB));
    	      }
    	      else
    	      { 
                break;
    	      }
            }	    
       	  }
        }
      }
#if PART_II  
      /* Use Induction Variable as Check Variable */
      LI = &getAnalysis<LoopInfo>();
      DT = &getAnalysis<DominatorTree>(); 

      for (LoopInfo::iterator LoopI = LI->begin(), LoopE = LI->end(); LoopI != LoopE; ++LoopI) {
        PHINode *phi = (*LoopI)->getCanonicalInductionVariable();
//        IndVars.insert(phi);
        if (phi)
          for (Loop::block_iterator LoopBblI = (*LoopI)->block_begin(), LoopBblE = (*LoopI)->block_end(); LoopBblI != LoopBblE; ++LoopBblI) {
            CheckTy * ChkInBbl = BblCheckMap[*LoopBblI];

	    for (CheckTy::iterator ChkI = ChkInBbl->begin(), ChkE = ChkInBbl->end(); ChkI != ChkE; ChkI++) {
              CheckValTy &check = ChkI->second;
	      Value *index = check.index;
              int32_t bound = check.bound;

	      if (index == phi)
	        continue;
	      else {
               for (Value::use_iterator IndI = phi->use_begin(), IndE = phi->use_end(); IndI != IndE; ++IndI) {

                  if (index == (*IndI)) {
                    switch (dyn_cast<Instruction>(index)->getOpcode()) {

		      case Instruction::Add:
		        for (User::op_iterator OprI = (*IndI)->op_begin(), OprE = (*IndI)->op_end(); OprI != OprE; ++OprI) {
                          if (ConstantInt *CI = dyn_cast<ConstantInt>(*OprI)) {
                            int32_t c = CI->getSExtValue();
  		            check.index = phi;
                            check.bound = bound - c;

			    break;
			  }
		        }

                        break;
		      case Instruction::Sub:
		        for (User::op_iterator OprI = (*IndI)->op_begin(), OprE = (*IndI)->op_end(); OprI != OprE; ++OprI) {
                          if (ConstantInt *CI = dyn_cast<ConstantInt>(*OprI)) {
                            int32_t c = CI->getSExtValue();
  		            check.index = phi;

			    if (OprI == (*IndI)->op_begin()) {
                              check.bound = c - bound + 1;
			      check.isUpper = !check.isUpper;
			    }
			    else
                              check.bound = bound + c;

			    break;
			  }
		        }
		      
		        break;
		      default:
		        break;
		    }
		  } 
	        }
	      }
	    }
	  }
      }

      /* Local Elimination */
      for (BblCheckMapTy::iterator MapI = BblCheckMap.begin(), MapE = BblCheckMap.end(); MapI != MapE; ++MapI) {
        CheckTy *ChkInBbl = MapI->second;
        
	for (CheckTy::iterator ChkI = ChkInBbl->begin(), ChkE = ChkInBbl->end(); ChkI != ChkE;) {
	  CheckValTy &check = ChkI->second;
	  Value *index = check.index;
          int32_t bound = check.bound;
          bool isUpper = check.isUpper;

	  /* Eliminate unnecessary constant index check*/
	  if (ConstantInt *CI = dyn_cast<ConstantInt>(index)) {
            int32_t indexVal = CI->getSExtValue();
	    
	    if (isUpper && indexVal >= bound) {
              cerr << "Exceed Upper Bound!" << endl;    
	    }
	    else if (!isUpper && indexVal < bound) {
              cerr << "Exceed Lower Bound!" << endl;
	    }

            ChkI = ChkInBbl->erase(ChkI);
	      
            goto ENDOFLOCAL;
	  }

	  for (CheckTy::iterator ChkI2 = ChkInBbl->begin(); ChkI2 != ChkI;) {
	    CheckValTy check2 = ChkI2->second;

	    /* Eliminate Subsumed Checks (size are different)*/
	    if (isSubsumedBound(check, check2)) {
              ChkI = ChkInBbl->erase(ChkI);

	      goto ENDOFLOCAL;
            }
            else if (isSubsumedBound (check2, check)) {
              ChkI2 = ChkInBbl->erase(ChkI2);

	      goto ENDOFSUBSUM;
	    }

	    ++ChkI2;

ENDOFSUBSUM:
            ;	    
	  }

          ++ChkI;

ENDOFLOCAL:
          ;
 	}
      }

      /************************************************************************************************/

      /* Global Elimination*/
      /* Find Busy Checks */
      /* GEN Set & Initialization */
      for (Function::iterator blk = F.begin(), blke = F.end(); blk != blke; ++blk) {
        CheckSetTy *GenInBbl = new CheckSetTy; 
        CheckSetTy *InInBbl = new CheckSetTy; 
        CheckSetTy *OutInBbl = new CheckSetTy; 
        BusyGen[blk] = GenInBbl;
        BusyIn[blk] = InInBbl;
        BusyOut[blk] = OutInBbl;

        CheckTy *ChkInBbl = BblCheckMap[blk];
        
	for (CheckTy::iterator ChkI = ChkInBbl->begin(), ChkE = ChkInBbl->end(); ChkI != ChkE; ++ChkI) {
	  CheckValTy check = ChkI->second;
//	  Value *index = check.first;

//	  if (IndVars.find(index) != IndVars.end()) {
            GenInBbl->insert(check);
	    unionIntoSet(&CheckDomain, &check);
//	  }
	}
      }  

      for (Function::iterator blk = F.begin(), blke = F.end(); blk != blke; ++blk) {
        *(BusyIn[blk]) = CheckDomain;
      }  
      
      /* Flow Algorithm */
      bool changeBusy;
      do {
        changeBusy = false;    
        
	for (Function::iterator blk = F.begin(), blke = F.end(); blk != blke; ++blk) {
          CheckSetTy *InInBbl = BusyIn[blk]; 
          CheckSetTy *oldOutInBbl = BusyOut[blk]; 
          CheckSetTy *GenInBbl = BusyGen[blk];
          CheckSetTy *newOutInBbl = new CheckSetTy; 
         
	  if (succ_begin(blk) != succ_end(blk))
	    *newOutInBbl = *BusyIn[*succ_begin(blk)];

	  for (succ_iterator SI = succ_begin(blk), SE = succ_end(blk); SI != SE; ++SI) {
	    intersectSet(newOutInBbl, BusyIn[*SI]);
  	  }
          	  
	  changeBusy |= compareSet(oldOutInBbl, newOutInBbl);
	  
	  BusyOut[blk] = newOutInBbl;
          delete oldOutInBbl;

	  *InInBbl = *newOutInBbl;
	  unionSet(InInBbl, GenInBbl);
        }

      } while(changeBusy);
      
      /* Modify Busy Checks*/
      for (Function::iterator blk = F.begin(), blke = F.end(); blk != blke; ++blk) {
        CheckSetTy *BusyOfBbl = BusyOut[blk]; 
        CheckTy *ChkInBbl = BblCheckMap[blk];
        
	for (CheckTy::iterator ChkI = ChkInBbl->begin(), ChkE = ChkInBbl->end(); ChkI != ChkE; ++ChkI) {
	  CheckValTy &check = ChkI->second;
	  Value *index = check.index;
          int32_t bound = check.bound;
          bool isUpper = check.isUpper;

	  for (CheckSetTy::iterator ChkI2 = BusyOfBbl->begin(), ChkE2 = BusyOfBbl->end(); ChkI2 != ChkE2; ++ChkI2) {
            Value *index2 = ChkI2->index;
            int32_t bound2 = ChkI2->bound;
            bool isUpper2 = ChkI2->isUpper;

	    if (isUpper && isUpper2) {
              if (index == index2) {
                if (bound > bound2)
	          check.bound = bound2;
	      } 
	    } 
	    else if (!isUpper && !isUpper2) {
              if (index == index2) {
                if (bound < bound2)
	          check.bound = bound2;
	      } 
	    }
	  }
	}
      }  
      
      /***************************************************************************************************************/

      /* Find Available Checks */
      /* GEN Set & Initialization */
      for (Function::iterator blk = F.begin(), blke = F.end(); blk != blke; ++blk) {
        CheckSetTy *GenInBbl = new CheckSetTy; 
        CheckSetTy *InInBbl = new CheckSetTy; 
        CheckSetTy *OutInBbl = new CheckSetTy; 
        AvailGen[blk] = GenInBbl;
        AvailIn[blk] = InInBbl;
        AvailOut[blk] = OutInBbl;

        CheckTy *ChkInBbl = BblCheckMap[blk];
        
	for (CheckTy::iterator ChkI = ChkInBbl->begin(), ChkE = ChkInBbl->end(); ChkI != ChkE; ++ChkI) {
	  CheckValTy check = ChkI->second;
//	  Value *index = check.first;

//	  if (IndVars.find(index) != IndVars.end()) {
            GenInBbl->insert(check);
//	    unionIntoSet(&CheckDomain, &check);
//	  }
	}
      }  

      for (Function::iterator blk = F.begin(), blke = F.end(); blk != blke; ++blk) {
        *(AvailOut[blk]) = CheckDomain;
      }  
      
      /* Flow Algorithm */
      bool changeAvail;
      do {
        changeAvail = false;    
        
	for (Function::iterator blk = F.begin(), blke = F.end(); blk != blke; ++blk) {
          CheckSetTy *OutOfBbl = AvailOut[blk]; 
          CheckSetTy *oldInOfBbl = AvailIn[blk]; 
          CheckSetTy *GenInBbl = AvailGen[blk];
          CheckSetTy *newInOfBbl = new CheckSetTy; 
         
	  if (pred_begin(blk) != pred_end(blk))
	    *newInOfBbl = *AvailOut[*pred_begin(blk)];

	  for (pred_iterator PI = pred_begin(blk), PE = pred_end(blk); PI != PE; ++PI) {
	    intersectSet(newInOfBbl, AvailOut[*PI]);
  	  }
          	  
	  changeAvail |= compareSet(oldInOfBbl, newInOfBbl);
	  
	  AvailIn[blk] = newInOfBbl;
          delete oldInOfBbl;

	  *OutOfBbl = *newInOfBbl;
	  unionSet(OutOfBbl, GenInBbl);
        }

      } while(changeAvail);

      /* Eliminate Redundant Checks*/
      for (Function::iterator blk = F.begin(), blke = F.end(); blk != blke; ++blk) {
        CheckSetTy *AvailOfBbl = AvailIn[blk]; 
        CheckTy *ChkInBbl = BblCheckMap[blk];
        
	for (CheckTy::iterator ChkI = ChkInBbl->begin(), ChkE = ChkInBbl->end(); ChkI != ChkE;) {
	  CheckValTy &check = ChkI->second;
	  Value *index = check.index;
          int32_t bound = check.bound;
          bool isUpper = check.isUpper;

	  for (CheckSetTy::iterator ChkI2 = AvailOfBbl->begin(), ChkE2 = AvailOfBbl->end(); ChkI2 != ChkE2; ++ChkI2) {
            Value *index2 = ChkI2->index;
            int32_t bound2 = ChkI2->bound;
            bool isUpper2 = ChkI2->isUpper;

	    if (isUpper && isUpper2) {
	      if (index == index2) {
                if (bound >= bound2) {
	          ChkI = ChkInBbl->erase(ChkI);

		  goto ENDOFELIMINATE;
	        }

	        break;
	      }
	    }
	    else if (!isUpper && !isUpper2) {
	      if (index == index2) {
                if (bound <= bound2) {
	          ChkI = ChkInBbl->erase(ChkI);

		  goto ENDOFELIMINATE;
	        }

	        break;
	      }
	    } 
	  }

	  ++ChkI;
ENDOFELIMINATE:	
          ;
	}
      }  
   
    /**********************************************************************************************/

      LoopQueue.clear(); 
      /* Propagation of Checks Out of Loops */
      for (LoopInfo::iterator LoopI = LI->begin(), LoopE = LI->end(); LoopI != LoopE; ++LoopI) {
	addLoopIntoQueue (*LoopI);
      }
      
      for (LoopQueueTy::iterator LoopI = LoopQueue.begin(), LoopE = LoopQueue.end(); LoopI != LoopE; ++LoopI) {
	BblCheckSetMapTy C;
	NDTy ND;
        bool isSimplified = (*LoopI)->isLoopSimplifyForm();	
	PHINode *phi = NULL;
        BasicBlock *PreHeader = NULL;
        SmallVector<BasicBlock*, 8> ExitingBlocks;
        Value * tripCount = NULL;
        unsigned phi_num = 0;
        Value * phi1 = NULL;
        Value * phi2 = NULL;
        Value * newindex = NULL;

        if (isSimplified) {
          phi = (*LoopI)->getCanonicalInductionVariable();
	  PreHeader = (*LoopI)->getLoopPreheader(); 
	  (*LoopI)->getExitingBlocks(ExitingBlocks);
          tripCount = (*LoopI)->getTripCount();
          
          if (phi) phi_num = phi->getNumIncomingValues();

	  if (phi_num == 2) {
            phi1 = phi->getIncomingValue(0);
	    phi2 = phi->getIncomingValue(1);

	    if (Instruction *Inst =  dyn_cast<Instruction>(phi1)) {
              if ((*LoopI)->contains(Inst->getParent()))
	        newindex = phi2;
	    }
	    else 
	      newindex = phi1;  
	  }
	}

	if (ExitingBlocks.size() && PreHeader/* && newindex*/) {
          /* Identify Candidates */
          for (Loop::block_iterator LoopBblI = (*LoopI)->block_begin(), LoopBblE = (*LoopI)->block_end(); LoopBblI != LoopBblE; ++LoopBblI) {
            CheckSetTy *COfBbl = new CheckSetTy; 
            C[*LoopBblI] = COfBbl;
            CheckTy * ChkInBbl = BblCheckMap[*LoopBblI];
  
	    for (CheckTy::iterator ChkI = ChkInBbl->begin(), ChkE = ChkInBbl->end(); ChkI != ChkE; ChkI++) {
              CheckValTy check = ChkI->second;
              Value* index = check.index;
	      bool isUpper = check.isUpper;
	      
	      if ((*LoopI)->isLoopInvariant(index)) COfBbl->insert(check);
	      else if (index == phi && !isUpper && newindex) COfBbl->insert(check);
	      else if (index == phi && isUpper && newindex && tripCount) COfBbl->insert(check);
	    }
	    
	    /* Initialize ND */
	    for (unsigned i = 0; i < ExitingBlocks.size(); i++) {
              if (!(DT->dominates(*LoopBblI, ExitingBlocks[i]))) {
                ND.insert(*LoopBblI);
		
		break;
	      }
	    }
	  }

	  /* Hoist */
	  bool loopChange = true;

	  while (loopChange) {
            loopChange = false;
 	    
	    for (Loop::block_iterator LoopBblI = (*LoopI)->block_begin(), LoopBblE = (*LoopI)->block_end(); LoopBblI != LoopBblE; ++LoopBblI) {
              bool continueFlag = false;

              for (succ_iterator SI = succ_begin(*LoopBblI), SE = succ_end(*LoopBblI); SI != SE; ++SI) {
	        if (ND.find(*SI) != ND.end()) {
                  continueFlag = true;
		  break;
		}
	      }

	      if (!continueFlag) continue;
              
	      for (succ_iterator SI = succ_begin(*LoopBblI), SE = succ_end(*LoopBblI); SI != SE; ++SI) {
	        if (!(*SI)->getUniquePredecessor()) {
                  continueFlag = false;
	          break;
	        }
	      }

	      if (!continueFlag) continue;
  
	      CheckSetTy prop; 

	      for (succ_iterator SI = succ_begin(*LoopBblI), SE = succ_end(*LoopBblI); SI != SE; ++SI) {
                if ((*LoopI)->contains(*SI)) {
                  prop = *C[*SI];
		  break;
		}
  	      }

	      for (succ_iterator SI = succ_begin(*LoopBblI), SE = succ_end(*LoopBblI); SI != SE; ++SI) {
                if ((*LoopI)->contains(*SI))
		  intersectSet(&prop, C[*SI]);
  	      }

	      if (prop.size()) {
                loopChange = true;
		TerminatorInst *InsertPos = (*LoopBblI)->getTerminator();

		for (CheckSetTy::iterator CI = prop.begin(), CE = prop.end(); CI != CE; ++CI) {
                  CheckValTy check;
		  check.index = CI->index;
		  check.bound = CI->bound;
		  check.isUpper = CI->isUpper;
              
		  C[*LoopBblI]->insert(check);
		  BblCheckMap[*LoopBblI]->push_back(make_pair(InsertPos, check));
                  for (succ_iterator SI = succ_begin(*LoopBblI), SE = succ_end(*LoopBblI); SI != SE; ++SI) {
                    if (!(*LoopI)->contains(*SI)) continue;

		    CheckSetTy::iterator CSetI = C[*SI]->find(check);

		    if (CSetI == C[*SI]->end()) continue;
		    else {
		      C[*SI]->erase(CSetI);
                      CheckTy * ChkInBbl = BblCheckMap[*SI];

                      for (CheckTy::iterator ChkI = ChkInBbl->begin(), ChkE = ChkInBbl->end(); ChkI != ChkE; ChkI++) {
			CheckValTy check2 = ChkI->second;

                        if (check2.index == check.index && check2.bound == check.bound && check2.isUpper == check.isUpper) {
                          ChkInBbl->erase(ChkI);

			  break;
			}
		      }
		    } 
  	          }
		}
       	      }
	    }
  	  }
	  
	  /* Propagate */
          TerminatorInst *InsertPos = PreHeader->getTerminator();

	  for (Loop::block_iterator LoopBblI = (*LoopI)->block_begin(), LoopBblE = (*LoopI)->block_end(); LoopBblI != LoopBblE; ++LoopBblI) {
            unsigned i;

            for (i = 0; i < ExitingBlocks.size(); i++) 
              if (!(DT->dominates(*LoopBblI, ExitingBlocks[i]))) break;
	      
	    if (i == ExitingBlocks.size()) {
              CheckTy * ChkInBbl = BblCheckMap[*LoopBblI];
  
              for (CheckTy::iterator ChkI = ChkInBbl->begin(), ChkE = ChkInBbl->end(); ChkI != ChkE; ) {
                CheckValTy &check = ChkI->second;
            
                if (C[*LoopBblI]->find(check) != C[*LoopBblI]->end()) {
                  if ((check.index != phi) || (check.index == phi && check.isUpper && tripCount) || (check.index == phi && !check.isUpper)) {
                    ChkI = ChkInBbl->erase(ChkI);
   		
                    if (check.index == phi && check.isUpper) {check.index = tripCount;check.bound++;}
                    else if (check.index == phi && !check.isUpper) check.index = newindex;
  
                    BblCheckMap[PreHeader]->push_back(make_pair(InsertPos, check));
  
                    goto ENDOFPROP;
		  }
  		}
  
                ++ChkI;
ENDOFPROP:
                ;	      
  	      }
  	    }
	  }
	}
      }

/*******************************************************************************************************/

      /* Local Elimination Again*/
      for (BblCheckMapTy::iterator MapI = BblCheckMap.begin(), MapE = BblCheckMap.end(); MapI != MapE; ++MapI) {
        CheckTy *ChkInBbl = MapI->second;
        
	for (CheckTy::iterator ChkI = ChkInBbl->begin(), ChkE = ChkInBbl->end(); ChkI != ChkE;) {
	  CheckValTy &check = ChkI->second;
	  Value *index = check.index;
          int32_t bound = check.bound;
          bool isUpper = check.isUpper;

	  /* Eliminate unnecessary constant index check*/
	  if (ConstantInt *CI = dyn_cast<ConstantInt>(index)) {
            int32_t indexVal = CI->getSExtValue();
	    
	    if (isUpper && indexVal >= bound) {
              cerr << "Exceed Upper Bound!" << endl;    
	    }
	    else if (!isUpper && indexVal < bound) {
              cerr << "Exceed Lower Bound!" << endl;
	    }

            ChkI = ChkInBbl->erase(ChkI);
	      
            goto ENDOFLOCAL2;
	  }

	  for (CheckTy::iterator ChkI2 = ChkInBbl->begin(); ChkI2 != ChkI;) {
	    CheckValTy check2 = ChkI2->second;

	    /* Eliminate Subsumed Checks (size are different)*/
	    if (isSubsumedBound(check, check2)) {
              ChkI = ChkInBbl->erase(ChkI);

	      goto ENDOFLOCAL2;
            }
            else if (isSubsumedBound (check2, check)) {
              ChkI2 = ChkInBbl->erase(ChkI2);

	      goto ENDOFSUBSUM2;
	    }

	    ++ChkI2;

ENDOFSUBSUM2:
            ;	    
	  }

          ++ChkI;

ENDOFLOCAL2:
          ;
 	}
      }
#endif
/****************************************************************************************************************/
#if PART_III
      BblRangeMapTy BblRangeMap;
      /* Path Analysis */    
      /* Set Range for every BBL */
      for (Function::iterator blk = F.begin(), blke = F.end(); blk != blke; ++blk) {
        ValRangeTy *rangeInBbl = new ValRangeTy; 
        BblRangeMap[blk] = rangeInBbl;
      }

      for (Function::iterator blk = F.begin(), blke = F.end(); blk != blke; ++blk) {
        for (BasicBlock::iterator I = blk->begin(), E = blk->end(); I != E; ++I) {
  
          if (ICmpInst *CmpI = dyn_cast<ICmpInst>(&*I)) {
            User::op_iterator OprI = CmpI->op_begin();
            User::op_iterator Opr1 = OprI;
            User::op_iterator Opr2 = ++OprI;
	    ICmpInst::Predicate pred = CmpI->getSignedPredicate();
	    Value * val = NULL;
            int32_t rangeTrue = -1, rangeFalse = -1;
            bool upperTrue = false, upperFalse = false;
 
 	    if (isa<ConstantInt>(*Opr1) && !isa<ConstantInt>(*Opr2)) {
 	      ConstantInt *CI = dyn_cast<ConstantInt>(*Opr1);
              int32_t range = CI->getSExtValue();
              val = *Opr2;

              switch(pred) {
 	        case ICmpInst::ICMP_SGT:
 		  rangeTrue = range;
 		  upperTrue = true;
 		  rangeFalse = range;
 		  upperFalse = false;
 		  break;
 	        case ICmpInst::ICMP_SGE:
                  rangeTrue = range + 1;
 		  upperTrue = true;
 		  rangeFalse = range + 1;
 		  upperFalse = false;
                  break;
 	        case ICmpInst::ICMP_SLT:
                  rangeTrue = range + 1;
 		  upperTrue = false;
 		  rangeFalse = range + 1;
 		  upperFalse = true;
                  break;
 	        case ICmpInst::ICMP_SLE:
                  rangeTrue = range;
 		  upperTrue = false;
 		  rangeFalse = range;
 		  upperFalse = true;
                  break;
 	        default:
                  break;
 	      }
 	    }
 	    else if (!isa<ConstantInt>(*Opr1) && isa<ConstantInt>(*Opr2)) {
 	      ConstantInt *CI = dyn_cast<ConstantInt>(*Opr2);
              int32_t range = CI->getSExtValue();
              val = *Opr1;

	      switch(pred) {
 	        case ICmpInst::ICMP_SGT:
                  rangeTrue = range + 1;
 		  upperTrue = false;
 		  rangeFalse = range + 1;
 		  upperFalse = true;
 		  break;
 	        case ICmpInst::ICMP_SGE:
                  rangeTrue = range;
 		  upperTrue = false;
 		  rangeFalse = range;
 		  upperFalse = true;
 		  break;
 	        case ICmpInst::ICMP_SLT:
 		  rangeTrue = range;
 		  upperTrue = true;
 		  rangeFalse = range;
 		  upperFalse = false;
 		  break;
 	        case ICmpInst::ICMP_SLE:
                  rangeTrue = range + 1;
 		  upperTrue = true;
 		  rangeFalse = range + 1;
 		  upperFalse = false;
 		  break;
 	        default:
                 break;
 	      }
 	    }
 
 	    if (rangeTrue != -1 || rangeFalse != -1) {
              for (Value::use_iterator I = CmpI->use_begin(), E = CmpI->use_end(); I != E; ++I) {
                if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
                  BasicBlock *BblTrue, *BblFalse;
		  BblTrue = BI->getSuccessor(0);
		  BblFalse = BI->getSuccessor(1);

	    	  for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) {
		    if (DT->dominates(BblTrue, BB)) {
                      ValRangeTy &RangeInBbl = (*BblRangeMap[BB]);
		     
		      if (RangeInBbl[val] == NULL) {
                        RangeInBbl[val] = new RangeTy;
			RangeInBbl[val]->first = numeric_limits<int32_t>::min();
			RangeInBbl[val]->second = numeric_limits<int32_t>::max();
		      }

		      RangeTy *Range = RangeInBbl[val];

		      if (upperTrue) {
                        if (rangeTrue < Range->second) Range->second = rangeTrue;
		      }
		      else {
                        if (rangeTrue > Range->first) Range->first = rangeTrue;
		      }
		    }
		    else if (DT->dominates(BblFalse, BB)) {
                      ValRangeTy &RangeInBbl = (*BblRangeMap[BB]);
		     
		      if (RangeInBbl[val] == NULL) {
                        RangeInBbl[val] = new RangeTy;
			RangeInBbl[val]->first = numeric_limits<int32_t>::min();
			RangeInBbl[val]->second = numeric_limits<int32_t>::max();
		      }

		      RangeTy *Range = RangeInBbl[val];

		      if (upperFalse) {
                        if (rangeFalse < Range->second) Range->second = rangeFalse;
		      }
		      else {
                        if (rangeFalse > Range->first) Range->first = rangeFalse;
		      }
		    }
                  }
		}
	      }	
 	    }
       	  }
        }
      }

      /* Path Elimination */
      for (BblCheckMapTy::iterator MapI = BblCheckMap.begin(), MapE = BblCheckMap.end(); MapI != MapE; ++MapI) {
        BasicBlock * BB = MapI->first;
      	CheckTy *ChkInBbl = MapI->second;
        ValRangeTy * RangeInBbl = BblRangeMap[BB];

        for (CheckTy::iterator ChkI = ChkInBbl->begin(), ChkE = ChkInBbl->end(); ChkI != ChkE;) {
	  CheckValTy check = ChkI->second;

	  if (RangeInBbl->find(check.index) != RangeInBbl->end()) {
	    RangeTy * range = RangeInBbl->find(check.index)->second;

            if (check.isUpper && range->second <= check.bound) {
              ChkI = ChkInBbl->erase(ChkI);
	      
	      goto ENDOFPATH;
	    }

	    if (check.isUpper && range->first >= check.bound) {
              ChkI = ChkInBbl->erase(ChkI);
              cerr << "Exceed Upper Bound!" << endl;
	      
	      goto ENDOFPATH;
	    }
            
	    if (!check.isUpper && range->second <= check.bound) {
              ChkI = ChkInBbl->erase(ChkI);
              cerr << "Exceed Lower Bound!" << endl;

	      goto ENDOFPATH;
	    }

	    if (!check.isUpper && range->first >= check.bound) {
              ChkI = ChkInBbl->erase(ChkI);

	      goto ENDOFPATH;
	    }
	  }

	  ++ChkI;
ENDOFPATH:
	  ;
        }
      }  
#endif
      /**********************************************************************************************************/ 

      /* Boundary Checks Code Generation */
      for (BblCheckMapTy::iterator MapI = BblCheckMap.begin(), MapE = BblCheckMap.end(); MapI != MapE; ++MapI) {
        CheckTy *ChkInBbl = MapI->second;

	if (ChkInBbl->size() > 0) Change = true;

        for (CheckTy::iterator ChkI = ChkInBbl->begin(), ChkE = ChkInBbl->end(); ChkI != ChkE; ++ChkI) {
          Instruction *InsrtPos = ChkI->first;
	  CheckValTy check = ChkI->second;

	  vector<Value*> Args(2);
          Args[0] = check.index;
          Args[1] = ConstantInt::get(Type::getInt32Ty(getGlobalContext()), check.bound);


          InsertCheckCall(Args, InsrtPos, check.isUpper);
        }
      }  
    	      
      return Change;
    }

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<LoopInfo>();
      AU.addRequired<DominatorTree>();
    }
  };
}

char InsertBoundChk::ID = 0;
static RegisterPass<InsertBoundChk>
X("phase1", "Phase 1 of CS6241");
